package com.hot100.mid;

/**
 * @author zhengTao
 * @version 1.0
 * @description:
 * @date 2022/10/2 12:44
 */
public class Demo45 {
    public static void main(String[] args) {

    }
    public int numSquares(int n) {
        if(check1(n)){
            return 1;
        }else if(check2(n)){
            return 2;
        }else if(check3(n)){
            return 3;
        }else {
            return 4;
        }
    }

    private boolean check3(int n) {
        for (int i = 1; i*i < n; i++) {
            if (check2(n-i*i)) {
                return true;
            }
        }
        return false;
    }

    //两个完全平方数
    private boolean check2(int n) {
        for (int i = 1; i*i < n; i++) {
            if (check1(n-i*i)) {
                return true;
            }
        }
        return false;
    }

    //本身就是完全平方数
    private boolean check1(int n) {
        int i= (int) Math.sqrt(n);
        return  n==i*i;
    }

}
